package 单周赛.september;

import java.util.*;

/**
 * @
 * @date 2024/04/14
 */
public class 第393场单周赛 {

    public static void main(String[] args) {

        System.out.println(findKthSmallest(new int[]{3, 6, 9}, 3));

    }

    public String findLatestTime(String s) {
        char[] chars = s.toCharArray();
        if (chars[0] == '?' && chars[1] == '?') {
            chars[0] = '1';
            chars[1] = '1';
        } else if (chars[0] == '?') {

            if (chars[1] == '0' || chars[1] == '1') {
                chars[0] = '1';
            } else {
                chars[0] = '0';
            }

        } else if (chars[1] == '?') {

            if (chars[0] == '1') {
                chars[1] = '1';
            } else {
                chars[1] = '9';
            }
        }


        if (chars[3] == '?') {
            chars[3] = '5';
        }
        if (chars[4] == '?') {
            chars[4] = '9';
        }
        return new String(chars);
    }


    private Set<Integer> primes = new HashSet<>();

    public int maximumPrimeDifference(int[] nums) {
        collectPrime(100);
        int minIdx = Integer.MAX_VALUE, maxIdx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (primes.contains(nums[i])) {
                minIdx = Math.min(minIdx, i);
                maxIdx = Math.max(maxIdx, i);
            }
        }

        return maxIdx - minIdx;
    }

    private void collectPrime(int max) {
        boolean[] record = new boolean[max + 1];
        for (int num = 2; num <= max; num++) {
            if (!record[num]) {
                primes.add(num);
            }

            int c = num;
            while ((long) num * c <= max) {
                record[num * c] = true;
                c++;
            }
        }
    }


    public static long findKthSmallest(int[] coins, int k) {
        Arrays.sort(coins);
        List<Integer> list = new ArrayList<>();
        int[] cnt = new int[26];
        for (int i = 0; i < coins.length - 1; i++) {
            int curCoin = coins[i];
            while (curCoin < coins[i + 1]) {
                list.add(coins[i]);
                cnt[coins[i]]++;
                curCoin += coins[i];
            }
        }
        list.add(coins[coins.length - 1]);
        cnt[coins[coins.length - 1]]++;


        int lastCoinIdx = k % (list.size() - 1);
        long totalCnt = (k / list.size()) * cnt[lastCoinIdx];

        long kth = list.get(lastCoinIdx) * totalCnt;

        for (int i = lastCoinIdx; i >= 0; i--) {
            if (list.get(lastCoinIdx) == list.get(i)) {
                kth += list.get(i);
            }
        }

        return kth;
    }
}
